public class Test1 {
    //leetcode 174 地下城游戏

    public int calculateMinimumHP(int[][] dungeon) {
        //1. 状态表示：这里不能用dp[i][j]表示从开始位置到当前位置所需要的最少的血量，因为当走到后面的
        //时候，随着后面关卡需要扣血，前面的dp表中的数据也是需要做出修改的，所以我们这里
        //dp[i][j]表示从当前位置开始到救出公主所需要的最低血量
        //2. 状态转移方程：dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-d[i][j],1)
        //这里状态转移方程为什么需要取min和1的最大值，因为如果min-d[i][j]的值为负数的话，就说明当前d[i][j]是一个可以加血的房间
        //就表示从当前位置到救出公主的位置所需要的最低的血量为负数，但是血量最低为1才可以
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 0 ; i <= m; i++) dp[i][n] = Integer.MAX_VALUE;
        for (int j = 0; j <= n; j++) dp[m][j] = Integer.MAX_VALUE;
        dp[m][n-1] = dp[m-1][n] = 1;
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                dp[i][j] = Math.max(Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j],1);
            }
        }
        return dp[0][0];
    }
}
